package array;

import java.util.HashMap;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 *
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 *
 */
public class leetCode560_subarraySum {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        // map：前缀和 -> 该前缀和出现的次数
        HashMap<Integer,Integer> map = new HashMap<>();
        // base case
        map.put(0,1);

        int result = 0;
        int sum_i = 0;
        for (int i = 0; i < n; i++) {
            sum_i += nums[i];
            int sum_j = sum_i - k;
            if(map.containsKey(sum_j)){
                result+=map.get(sum_j);
            }
            map.put(sum_i,map.getOrDefault(sum_i,0) + 1);
        }
        return result;

    }

    public int subarraySum2(int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int result = 0;
        int sum1 = 0;
        for (int i = 0; i < n; i++) {
            sum1 += nums[i];
            int sum2 = sum1 - k;
            if(map.containsKey(sum2)){
                result += map.get(sum2);
            }
            map.put(sum1,map.getOrDefault(sum1,0) + 1);
        }
        return result;

    }

    public int subarraySum3(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int result = 0;
        int sum1 = 0;
        for (int i = 0; i < nums.length; i++) {
            sum1 += nums[i];
            int sum2 = sum1 - k;
            if(map.containsKey(sum2)){
                result += map.get(sum2);
            }
            map.put(sum1,map.getOrDefault(sum1,0) + 1);
        }
        return result;
    }

    public static void main(String[] args) {
        leetCode560_subarraySum a = new leetCode560_subarraySum();
        int[] nums = {1,2,3};
        a.subarraySum3(nums,3);
    }
}
